//
// Created by francklinson on 2021/9/1 AT 10:51.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>

using namespace std;

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval) {
        // 可以直接把新的区间放入  再按照56题的模式走
        // 能不能用到二分？
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end(), [](vector<int> &a, vector<int> &b) {
            return a[0] < b[0];
        });
        vector<vector<int>> ans;
        // 把最初的放进去
        ans.push_back(intervals[0]);
        // 合并
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i][0] <= ans.back()[1]) {
                // 可以合并
                ans.back()[1] = max(intervals[i][1], ans.back()[1]);
            } else {
                ans.push_back(intervals[i]);
            }
        }
        return ans;
    }
};

class Solution2 {  // 题解 模拟
public:
    vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        bool placed = false;
        vector<vector<int>> ans;
        for (const auto &interval: intervals) {
            if (interval[0] > right) {
                // 遇到了插入区间的右侧区间插入结束
                // 在插入区间的右侧且无交集
                if (!placed) {
                    ans.push_back({left, right});
                    placed = true;
                }
                ans.push_back(interval);
            } else if (interval[1] < left) {
                // 在插入区间的左侧且无交集
                ans.push_back(interval);
            } else {
                // 与插入区间有交集，计算它们的并集
                left = min(left, interval[0]);
                right = max(right, interval[1]);
            }
        }
        if (!placed) {
            ans.push_back({left, right});
        }
        return ans;
    }
};

int main() {
    vector<vector<int>> intervals{{1,  2},
                                  {3,  5},
                                  {6,  7},
                                  {8,  10},
                                  {12, 16}};
    vector<int> newInterval{4, 8};
    Solution2 solution;
    vector<vector<int>> ans = solution.insert(intervals, newInterval);
    for (vector<int> &x: ans) {
        for (int &y: x) {
            cout << y << " ";
        }
        cout << endl;
    }
    return 0;
}

